#include<iostream>
#include<algorithm>
using namespace std;
const int N = 6e3 + 10;
struct node
{
	int a, b, w;
}S[N];
int p[N], sz[N];
int n;
int find(int x)
{
	if (x != p[x])p[x] = find(p[x]);
	return p[x];
}
int cmp(node a, node b)
{
	return a.w < b.w;
}
int main()
{
	int t;
	cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 0; i < n - 1; i++) {
			int a, b, c;
			cin >> a >> b >> c;
			S[i] = { a,b,c };
		}
		for (int i = 1; i <= n; i++) {
			p[i] = i;
			sz[i] = 1;
		}
		sort(S, S + n - 1, cmp);
		int ans = 0;
		for (int i = 0; i < n - 1; i++) {
			int a = S[i].a;
			int b = S[i].b;
			int w = S[i].w;
			a = find(a);
			b = find(b);
			if (a != b) {
				//cout << "sz[a]==" << sz[a] << "   sz[b]==" << sz[b] << endl;
				ans += (sz[a] * sz[b] - 1) * (w + 1);
				p[a] = b;
				sz[b] += sz[a];
			}
		}
		cout << ans << endl;
	}
	return 0;
}